import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Sort {
    //归并排序
    private void mergeFunc(int[] array , int left, int right){
        if(left == right){
            return;
        }
        int mid = (left + right) / 2;
        mergeFunc(array, left, mid);
        mergeFunc(array, mid + 1, right);
        merge(array, left, right, mid);
    }
    private void merge(int[] array, int start, int end, int mid){
        int[] tmpArr = new int[end - start + 1];
        int s1 = start;
        int s2 = mid + 1;
        int k = 0;
        while(s1 <= mid && s2 <= end){
            if(array[s1] < array[s2]) {
                tmpArr[k++] = array[s1++];
            }else{
                tmpArr[k++] = array[s2++];
            }
        }
        while(s1 <= mid){
            tmpArr[k++] = array[s1++];
        }
        while(s2 <=end){
            tmpArr[k++] = array[s2++];
        }
        for(int i = 0; i < tmpArr.length; i++){
            array[start + i] = tmpArr[i];
        }
    }
    public void mergeSort(int[] array){
        mergeFunc(array, 0, array.length - 1);
    }
    //top-k问题
    public int[] topK(int[] array, int k){
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>(){
            @Override
            public int compare(Integer o1, Integer o2){
                return o1 - o2;
            }
        });
        int[] retArr = new int[k];
        for(int i = 0; i < array.length; i++){
            if(i < k){
                priorityQueue.offer(array[i]);
            }else if(priorityQueue.peek() < array[i]){
                    priorityQueue.offer(array[i]);
                    priorityQueue.poll();
            }
        }
        for(int i = 0; i < k; i++){
            retArr[i] = priorityQueue.poll();
        }
        return retArr;

    }
}

